\section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:intro}

%Motivate the problem
%Give a summary of the paper: what you did and how
%Explicitly state your contribution

Pattern matching is an abstraction supported by many programming languages.
It allows the user tersely to describe a (possibly infinite) set of 
values accepted by the pattern. A \emph{pattern} represents a predicate on 
values, and is usually  much more concise and readable than the 
equivalent predicate spelled out as imperative code.

Popularized by functional programming community, most notably Hope\cite{BMS80}, 
ML\cite{ML90}, Miranda\cite{Miranda85} and Haskell\cite{Haskell98Book}, for 
providing syntax very close to mathematical notations.
From there, it has 
found its way into many imperative programming languages e.g. 
Pizza\cite{Odersky97pizzainto}, Scala\cite{Scala2nd}, Fortress\cite{RPS10}, as 
well as dialects of Java\cite{Liu03jmatch:iterable,HydroJ2003}, C++\cite{Prop96}, 
Eiffel\cite{Moreau:2003} and others. It is relatively easy to provide a form of pattern 
matching when designing a new language, but to introduce it into a language in 
widespread use is a challenge. The obvious utility of the feature may be 
compromised by the need to fit into the language's syntax, semantics, and tool 
chains. A prototype implementation requires more effort than for an experimental 
language and is harder to get into use because mainstream users are unwilling 
to try non-portable, non-standard, and unoptimized features.

To balance the utility and effort we decided to take the Semantically 
Enhanced Library Language (SELL) approach\cite{SELL}. We provide the
general-purpose programming language with a library, extended with a tool 
support. This will typically (as in this case) not provide you 100\% of the functionality that a 
language extension would do, but it allows experimentation and special-purpose use
with existing compilers and tool chains. With pattern matching, we managed to avoid 
external tool support by relying on some pretty nasty macro hacking to provide a
conventional and convenient interface to an efficient library implementation.
By efficient, we mean about as fast as functional languages for closed cases and
much better than code generated for visitor patterns by commercial optimizers 
for open cases\cite{TypeSwitch}.

Our current solution is a proof of concept that sets a minimum threshold for 
performance, brevity, clarity and usefulness of a language solution for pattern 
matching in C++. It provides full functionality, so we can experiment with use 
of pattern matching in C++ and with language alternatives. To give an idea of 
what our library offers, consider an example from a domain where pattern matching 
is considered to provide terseness and clarity -- compiler construction. 
Consider for example a simple language of expressions:

\begin{lstlisting}
@$exp$ \is{} $val$ \Alt{} $exp+exp$ \Alt{} $exp-exp$ \Alt{} $exp*exp$ \Alt{} $exp/exp$@
\end{lstlisting}

\noindent
An OCaml data type describing this grammar as well as a simple evaluator of expressions 
in it, can be declared as following:

\begin{lstlisting}[language=Caml,keepspaces,columns=flexible]
type expr = Value of int 
          | Plus  of expr * expr | Minus  of expr * expr 
          | Times of expr * expr | Divide of expr * expr
          ;;

let rec eval e =
  match e with
            Value  v      -> v
          | Plus   (a, b) -> (eval a) + (eval b)
          | Minus  (a, b) -> (eval a) - (eval b)
          | Times  (a, b) -> (eval a) * (eval b)
          | Divide (a, b) -> (eval a) / (eval b)
          ;;
\end{lstlisting}

\noindent
The corresponding C++ data types would most likely be parameterized, but for
now we will just use simple classes:

\begin{lstlisting}[keepspaces,columns=flexible]
struct Expr { virtual @$\sim$@Expr() {} };
struct Value  : Expr { int value; };
struct Plus   : Expr { Expr* exp1; Expr* exp2; };
struct Minus  : Expr { Expr* exp1; Expr* exp2; };
struct Times  : Expr { Expr* exp1; Expr* exp2; };
struct Divide : Expr { Expr* exp1; Expr* exp2; };
\end{lstlisting}

\noindent
Using our library, we can express matching about as tersely as OCaml:

\begin{lstlisting}[keepspaces,columns=flexible]
int eval(const Expr& e)
{
    Match(e)
    {
      Case(Value,  n)    return n;
      Case(Plus,   a, b) return eval(a) + eval(b);
      Case(Minus,  a, b) return eval(a) - eval(b);
      Case(Times,  a, b) return eval(a) * eval(b);
      Case(Divide, a, b) return eval(a) / eval(b);
    }
    EndMatch
}
\end{lstlisting}

\noindent
To make the example fully functional we need to provide mappings of binding 
positions to corresponding class members:

\begin{lstlisting}[keepspaces,columns=flexible]
template <> struct bindings<Value>  { CM(0,Value::value); };
template <> struct bindings<Plus>   { CM(0,Plus::exp1); 
  ...                                 CM(1,Plus::exp2);   };
template <> struct bindings<Divide> { CM(0,Divide::exp1); 
                                      CM(1,Divide::exp2); };
\end{lstlisting}

\noindent
This binding code would be implicitly provided by the compiler had
we chosen that implementation strategy.

The syntax is provided without any external tool support. Instead we rely on a 
few C++11 features~\cite{C++11}, template meta-programming, and macros. It runs 
about as fast as OCaml and Haskell equivalents (\textsection\ref{sec:ocaml}), and, depending 
on the usage scenario, compiler and underlying hardware, comes close or 
outperforms the handcrafted C++ code based on the \emph{visitor design pattern} 
(\textsection\ref{sec:eval}).

\subsection{Motivation}

The ideas and the 
\emph{Mach7} library were motivated by our unsatisfactory experiences working 
with various \Cpp{} front-ends and program analysis frameworks~\cite{Pivot09,gdr-2012:liz,Phoenix,Clang}. 
The problem was not in the frameworks per se, but in the fact that we had to use
the \emph{visitor design pattern}~\cite{DesignPatterns1993} to inspect, traverse, and 
elaborate abstract syntax trees of target languages. We found visitors 
unsuitable to express application logic directly, surprisingly hard to teach 
students, and often slower than handcrafted workaround techniques. 
We found dynamic casts in many places, often nested, 
because users wanted to answer simple structural 
questions without having to resort to visitors. Users preferred shorter, cleaner, 
and more direct code to visitors, even at a high cost in performance (assuming 
that the programmer knew the cost). The usage of \code{dynamic\_cast} resembled 
the use of pattern matching in functional languages to unpack algebraic data 
types. Thus, our initial goal was to develop a domain-specific library for C++ 
to express various predicates on tree-like structures as elegantly as is done in functional 
languages. This grew into a general high-performance pattern-matching library.

The library is the latest in a series of 7 libraries. The earlier versions were 
superceded because they failed to meet our standards for notation, performance, 
or generality. Our standard is set by the principle that a fair comparison must 
be against the gold standard in a field. For example, if we work on a linear 
algebra library, we must compare to Fortran or one of the industrial C++ 
libraries, rather than Java or C. For pattern matching we chose optimized OCaml 
as our standard for closed (compile-time polymorphic) sets of classes and C++ 
for uses of the visitor pattern. For generality and simplicity of use, we deemed 
it essential to do both with a uniform syntax.

\subsection{The Expression Problem}
\label{sec:exp}

%Expression problem is a problem of supporting in a programming language modular 
%extensibility of both data and functions at the same time. Functional languages
%allow for easy addition of new functions at the expense of disallowing new data
%variants. Object-oriented languages allow for easy addition of new variants at 
%the expense of disallowing new functions. Many attempts have been made to 
%resolve this dilema in both camps, nevertheless no universally accepted solution 
%that is modular, open and efficient has been found.

%Visitor Design Pattern has became de-facto standard in dealing with expression 
%problem in many industry-strength object-oriented languages because of two 
%factors: its speed and being a library solution. It comes at the cost of 
%restricting extensibility of data, increased verbosity and being hard to teach 
%and understand, but nevertheless, remains the weapon of choice for interacting 
%with numerous object-oriented libraries and frameworks. 

Type switching is related to a more general problem manifesting the differences 
in functional and object-oriented programming styles.
Conventional algebraic datatypes, as found in most functional languages, allow 
for easy addition of new functions on existing data types. However, they fall short 
in extending data types themselves (e.g. with new constructors), which requires 
modifying the source code. Object-oriented languages make 
data type extension trivial through inheritance, but the addition of new 
functions operating on these classes typically requires changes to the class 
definition. This dilemma is known as the \emph{expression problem}~\cite{Cook90,exprproblem}.

Classes differ from algebraic data types in two important ways. Firstly, they
are \emph{extensible}, for new variants can be added later by inheriting from
the base class. Secondly, they are \emph{hierarchical} and thus typically 
\emph{non-disjoint} since variants can be inherited from other variants and form 
a subtyping relation between themselves~\cite{Glew99}. In contrast, variants in 
conventional algebraic data types are \emph{disjoint} and \emph{closed}.
Some functional languages e.g. ML2000~\cite{ML2000} and its predecessor, Moby, 
were experimenting with \emph{hierarchical extensible sum types}, which are 
closer to object-oriented classes then algebraic data types are, but, 
interestingly, they provided no %neither traditional nor efficient 
facilities for performing case analysis on them.

Functional languages allow for the easy addition of new functions on existing data 
types, but fall short in extending data types themselves (e.g. with new constructors), 
which requires modifying the source code. Object-oriented languages, on the 
other hand, make data type extension trivial through inheritance, but the addition 
of new functions that work on these classes typically requires changes to the class 
definition. This dilemma was first discussed by Cook~\cite{Cook90} and then 
accentuated by Wadler~\cite{exprproblem} under the name \emph{expression problem}. Quoting Wadler:

\emph{``The Expression Problem is a new name for an old problem. The goal is
to define a datatype by cases, where one can add new cases to the
datatype and new functions over the datatype, without recompiling
existing code, and while retaining static type safety (e.g., no
casts)''}.

To better understand the problem, note that classes differ from algebraic data 
types in two important ways: they are \emph{extensible} since new variants can 
be added by inheriting from the base class, as well as \emph{hierarchical} and 
thus \emph{non-disjoint} since variants can be inherited from other variants and 
form a subtyping relation between themselves~\cite{Glew99}. This is not the case 
with traditional algebraic data types in functional languages, where the set of 
variants is \emph{closed}, while the variants are \emph{disjoint}. Some 
functional languages e.g. ML2000~\cite{ML2000} and Moby~\cite{Moby} were 
experimenting with \emph{hierarchical extensible sum types}, which are closer to 
object-oriented classes then algebraic data types are, but, interestingly, they 
did not provide pattern matching facilities on them!

Zenger and Odersky refined the expression problem in the context of 
independently extensible solutions~\cite{fool12} as a challenge to find an 
implementation technique that satisfies the following requirements:
%
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\item \emph{Extensibility in both dimensions}: It should be possible to add new 
      data variants, while adapting the existing operations accordingly. It 
      should also be possible to introduce new functions. 
\item \emph{Strong static type safety}: It should be impossible to apply a 
      function to a data variant, which it cannot handle. 
\item \emph{No modification or duplication}: Existing code should neither be 
      modified nor duplicated.
\item \emph{Separate compilation}: Neither datatype extensions nor addition of 
      new functions should require re-typechecking the original datatype or 
      existing functions. No safety checks should be deferred until link or 
      runtime.
\item \emph{Independent extensibility}: It should be possible to combine 
      independently developed extensions so that they can be used jointly.
\end{itemize}

%Paraphrasing, the expression problem can be summarized as a problem of 
%supporting modular extensibility of both data and functions at the same time in 
%one programming language.

\noindent
Object-oriented languages further complicate the matter with the fact that 
data variants are not necessarily disjoint and may form subtyping relationships  
between themselves. We thus introduced an additional requirement based on the
Liskov substitution principle~\cite{Lis87}:

\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\item \emph{Substitutability}: Operations expressed on more general data variants
      should be applicable to ones that are more specific
      (the latter being in a subtyping relation with the former).
\end{itemize}

%Depending on the semantics of the language's subtyping relation, 
%substitutability requirement may turn pattern matching into an expensive 
%operation. OCaml, for example, that uses structural subtyping on its object 
%types, does not offer pattern 

\noindent
We will refer to a solution that satisfies all of the above requirements as \emph{open}. 
Numerous solutions have been proposed to dealing with the expression problem in both 
functional~\cite{garrigue-98,LohHinze2006} and object-oriented 
camps~\cite{Palsberg98,Krishnamurthi98,Zenger:2001,runabout}, but very few have
made their way into one of the mainstream languages. We refer the reader to Zenger 
and Odersky's original manuscript for a discussion of the approaches~\cite{fool12}. 
Interestingly, most of the discussed object-oriented solutions focused on the visitor design pattern~\cite{DesignPatterns1993} and its extensions, 
which even today seem to be the most commonly used approach to dealing with the 
expression problem in object-oriented languages.

\subsection{Visitor Design Pattern}
\label{sec:vdp}

%Discuss visitor design pattern and its problems.
%\begin{itemize}
%\item Intrusive - requires changes to the hierarchy
%\item Not open  - addition of new classes changes visitor interface
%\item Does not provide by default relation between visitors of base and derived classes
%\item Control inversion
%\item Cannot be generically extended to handling n arguments
%\end{itemize}

The \emph{visitor design pattern}~\cite{DesignPatterns1993} was devised to solve the problem 
of extending existing classes with new functions in object-oriented languages. 
Consider the above Expr example and imagine that in addition to evaluation we would like to also provide a pretty 
printing of expressions. A typical object-oriented approach would be to 
introduce a virtual function \\ \code{virtual void print() const = 0;} inside 
the abstract base class \code{Expr}, which will be implemented correspondingly 
in all the derived classes. This works well as long as we know all the required  
operations on the abstract class in advance. Unfortunately, this is very 
difficult to achieve in reality as the code evolves, especially in a production 
environment. To put this in context, imagine that after the above interface with 
pretty-printing functionality has been deployed, we decided that we need 
similar functionality that saves the expression in XML format. Adding new 
virtual function implies modifying the base class and creating a versioning 
problem with the code that has been deployed already using the old interface.

To alleviate this problem, the Visitor Design Pattern separates the 
\emph{commonality} of all such future member-functions from their 
\emph{specifics}. The former deals with identifying the most-specific derived 
class of the receiver object known to the system at the time the base class was 
designed. The latter provides implementation of the required functionality once 
the most-specific derived class has been identified. The interaction between the 
two is encoded in the protocol that fixes a \emph{visitation interface} 
enumerating all known derived classes on one side and a dispatching mechanism 
that guarantees to select the most-specific case with respect to the dynamic 
type of the receiver in the visitation interface. An implementation of this 
protocol for our Expr example might look like the following:

\begin{lstlisting}
// Forward declaration of known derived classes
struct Value; struct Plus; ... struct Divide;
@\halfline@
// Visitation interface
struct ExprVisitor
{
    virtual void visit(const Value&)  = 0;
    virtual void visit(const Plus&)   = 0;
    ...  // One virtual function per each known derived class
    virtual void visit(const Divide&) = 0;
};
@\halfline@
// Abstract base and known derived classes
struct Expr { 
    virtual void accept(ExprVisitor&) const = 0; };
struct Value : Expr { ...
    void accept(ExprVisitor& v) const { v.visit(*this); } };
struct Plus  : Expr { ...
    void accept(ExprVisitor& v) const { v.visit(*this); } };
\end{lstlisting}

\noindent
Note that even though implementations of \code{accept} member-functions in all 
derived classes are syntactically identical, a different \code{visit} is called. 
We rely here on the overload resolution mechanism of C++ to pick the most 
specialized \code{visit} member-function applicable to the static type of 
\code{*this}.

%This mere code 
%maintenance convenience unfortunately, often confuses novices on what 
%is going on. We thus would like to point out that member-functions in the 
%visitation interface are not required to be called with the same name, -- we 
%could have equally well called them \code{visit_value}, \code{visit_plus} etc. 
%making the corresponding changes to calls inside \code{Value::accept}, 
%\code{Plus::accept} etc.

A user can now implement new functions by overriding \code{ExprVisitor}'s 
functions. For example:

\begin{lstlisting}
std::string to_str(const Expr* e) // Converts expressions to string
{
  struct ToStrVisitor : ExprVisitor
  {
    void visit(const Value& e) { result = std::to_string(e.value); }
    ...
    void visit(const Divide& e) { 
        result = to_str(e.exp1) + '/' + to_str(e.exp2); 
    }
    std::string result;
  } v;
  e->accept(v);
  return v.result;
}
\end{lstlisting}

\noindent
The function \code{eval} we presented above, as well as any new function that we 
would like to add to \code{Expr}, can now be implemented in much the same way, 
without the need to change the base interface. This flexibility does not come for free, 
though, and we would like to point out some pros and cons of this solution.

The most important advantage of the visitor design pattern is the {\bf possibility 
to add new operations} to the class hierarchy without the need to change 
the interface. Its second most-quoted advantage is {\bf speed} -- the 
overhead of two virtual function calls incurred by the double  
dispatch present in the visitor design pattern is often negligible on modern 
architectures. Yet another advantage that often remains unnoticed is that the 
above solution achieves extensibility of functions with {\bf library only means} 
by using facilities already present in the language. Nevertheless, there are 
quite a few disadvantages.

The solution is {\bf intrusive} since we had to inject syntactically the same 
definition of the \code{accept} method into every class participating in visitation. 
It is also {\bf specific to hierarchy}, as we had to declare a visitation 
interface specific to the base class. The amount of {\bf boilerplate code} 
required by visitor design pattern cannot go unnoticed. It also increases with 
every argument that has to be passed into the visitor to be available during the 
visitation. This aspect can be seen in the example from \textsection\ref{sec:xmpl} 
where we have to store both functors inside the visitor.

More importantly, visitors {\bf hinder extensibility} of the class hierarchy: 
new classes added to the hierarchy after the visitation interface has been 
fixed will be treated as their most derived base class present in the interface.
A solution to this problem has been proposed in the form of \emph{Extensible 
Visitors with Default Cases}~\cite[\textsection 4.2]{Zenger:2001}; however, the 
solution, after remapping it onto C++, has problems of its own, discussed in 
detail in related work in \textsection\ref{sec:rw}.

%The visitation interface 
%hierarchy can easily be grown linearly (adding new cases for the new classes in 
%the original hierarchy each time), but independent extensions by different  
%authorities require developer's intervention to unify them all, before they can 
%be used together. This may not be feasible in environments that use dynamic 
%linking. To avoid writing even more boilerplate code in new visitors, the 
%solution would require usage of virtual inheritance, which typically has 
%an overhead of extra memory dereferencing. On top of the double dispatch already 
%present in the visitor pattern, the solution will incur two additional virtual 
%calls and a dynamic cast for each level of visitor extension. Additional double 
%dispatch is incurred by forwarding of default handling from base visitor to a 
%derived one, while the dynamic cast is required for safety and can be replaced 
%with a static case when visitation interface is guaranteed to be grown linearly 
%(extended by one authority only). Yet another virtual call is required to be 
%able to forward computations to subcomponents on tree-like structures to the 
%most derived visitor. This last function lets one avoid the necessity of using 
%heap to allocate a temporary visitor through the \emph{Factory Design 
%Pattern}\cite{DesignPatterns1993} used in \emph{Extensible Visitor} solution 
%originally proposed by Krishnamurti, Felleisen and Friedman\cite{Krishnamurthi98}.

Once all the boilerplate related to visitors has been written and the visitation 
interface has been fixed we are still left with some annoyances incurred by the 
pattern. One of them is the necessity to work with the {\bf control inversion} 
that visitors put in place. Because of it we have to save any local state and 
any arguments that some of the \code{visit} callbacks might need from the 
calling environment. Similarly, we have to save the result of the visitation, 
as we cannot assume that all the visitors that will potentially be implemented 
on a given hierarchy will use the same result type. Using visitors in a generic 
algorithm requires even more precautions. We summarize these visitor-related 
issues in the following motivating example, followed by an illustration of a 
pattern-matching solution to the same problem enabled with our library.

\subsection{Motivating Example}
\label{sec:xmpl}

While comparing generic programming facilities available to functional and 
imperative languages (mainly Haskell and C++), Dos Reis and J\"arvi present the 
following example in Haskell describing a sum functor\cite{DRJ05}:

\begin{lstlisting}[language=Haskell,keepspaces]
data Either a b = Left a | Right b
@\halfline@
eitherLift :: (a -> c) -> (b -> d) -> Either a b -> Either c d
eitherLift f g (Left  x) = Left  (f x)
eitherLift f g (Right y) = Right (g y)
\end{lstlisting}

\noindent
In simple words, the function \codehaskell{eitherLift} above takes two functions and an 
object and depending on the actual type constructor the object was created with, 
calls first or second function on the embedded value, encoding the result 
correspondingly.

Its equivalent in C++ is not straightforward. Idiomatic, type-safe, handling of 
discriminated unions in C++ typically assumes use of the \emph{Visitor Design Pattern}\cite{DesignPatterns}, 
which in this case amounts to 25 lines of ``boiler plate code'' plus 14 lines 
of the specific functionality.

\begin{lstlisting}
template <class X, class Y> class Either;
template <class X, class Y> class Left;
template <class X, class Y> class Right;
@\halfline@
template <class X, class Y>
struct EitherVisitor {
    virtual void visit(const  Left<X,Y>&) = 0;
    virtual void visit(const Right<X,Y>&) = 0;
};
@\halfline@
template <class X, class Y>
struct Either {
    virtual @$\sim$@Either() {}
    virtual void accept(EitherVisitor<X,Y>& v) const = 0;
};
@\halfline@
template <class X, class Y>
struct Left : Either<X,Y> {
    const X& x;
    Left(const X& x) : x(x) {}
    void accept(EitherVisitor<X,Y>& v) const { v.visit(*this); }
};
@\halfline@
template <class X, class Y>
struct Right : Either<X,Y> {
    const Y& y;
    Right(const Y& y) : y(y) {}
    void accept(EitherVisitor<X,Y>& v) const { v.visit(*this); }
};
\end{lstlisting}

\noindent
The code above defines the necessary parameterized data structures as well as a 
correspondingly parameterized visitor class capable of introspecting it at 
run-time. The authors agree with us \emph{``The code has a fair amount of 
boilerplate to simulate pattern matching...''}\cite{DRJ05} The actual 
implementation of \codehaskell{lift} in C++ now amounts to declaring and 
invoking a visitor:

\begin{lstlisting}
template <class X, class Y, class S, class T>
const Either<S,T>& eitherLift(const Either<X,Y>& e, S f(X), T g(Y))
{
    typedef S (*F)(X);
    typedef T (*G)(Y);
    struct Impl : EitherVisitor<X,Y> {
        F f;
        G g;
        const Either<S,T>* value;
        Impl(F f, G g) : f(f), g(g), value() {}
        void visit(const Left<X,Y>& e) {
            value = left<S,T>(f(e.x));
        }
        void visit(const Right<X,Y>& e) {
            value = right<S,T>(g(e.y));
        }
    };
    Impl vis(f, g);
    e.accept(vis);
    return *vis.value;
}
\end{lstlisting}

\noindent
The same function expressed with our pattern-matching facility seems to be much 
closer to the original Haskell definition:

\begin{lstlisting}[keepspaces,columns=flexible]
template <class X, class Y, class S, class T>
const Either<S,T>* lift(const Either<X,Y>& e, S f(X), T g(Y))
{
    Match(e)
      Case(( Left<X,Y>), x) return  left<S,T>(f(x));
      Case((Right<X,Y>), y) return right<S,T>(g(y));
    EndMatch
}
\end{lstlisting}

\noindent
This is also as fast as the visitor solution, but unlike the visitors based 
approach it neither requires \code{EitherVisitor}, nor any of the injected 
\code{accept} member-functions. We do require binding definitions though to be 
able to bind variables \code{x} and \code{y}:

%@\footnote{We need to take the first argument in parentheses to avoid interpretation of comma in template argument list by the preprocessor}@
%\footnote{Definitions of obvious functions \code{left} and \code{right} have 
%been ommitted in both cases.}

\begin{lstlisting}[keepspaces,columns=flexible]
template <class X, class Y> 
    struct bindings<Left<X,Y>>  { CM(0, Left<X,Y>::x); };
template <class X, class Y> 
    struct bindings<Right<X,Y>> { CM(0,Right<X,Y>::y); };
\end{lstlisting}

\noindent
Note that these binding definitions are made once for all possible instantiations 
with the use of partial template specialization in C++ and would not be needed 
if we implemented pattern matching in a compiler rather than a library.

\subsection{Summary}

The contributions of the paper are twofold and can be summarized as following:

\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\item We present techniques based on memoization (\textsection\ref{sec:copc}) and 
class precedence list (\textsection\ref{sec:cotc}) that can be used to implement 
type switching efficiently based on the run-time type of the argument.

  \begin{itemize}
  \setlength{\itemsep}{0pt}
  \setlength{\parskip}{0pt}
  \item The techniques come close and often outperform its de facto contender -- 
        visitor design pattern -- without sacrificing extensibility (\textsection\ref{sec:eval}).
  \item They work in the presence of multiple inheritance, including repeated and 
        virtual inheritance, as well as in generic code (\textsection\ref{sec:vtblmem}).
  \item The solution is open by construction (\textsection\ref{sec:poets}), 
        non-intrusive, and avoids the control inversion typical for visitors.
  \item It applies to polymorphic (\textsection\ref{sec:vtp}-\ref{sec:vtblmem}) and 
        tagged (\textsection\ref{sec:cotc}) class hierarchies through a unified  
        syntax~\cite{AP}.
  \item Our memoization device (\textsection\ref{sec:memdev}) generalizes to 
        other languages and can be used to implement type switching 
        (\textsection\ref{sec:vtblmem}), type testing 
        (\textsection\ref{sec:poets},\cite[\textsection 4.7]{TR}), predicate dispatch 
        (\textsection\ref{sec:memdev}), and multiple dispatch 
        (\textsection\ref{sec:cc}) efficiently.
  \item We list conditions under which virtual table pointers, commonly used in 
        C++ implementations, uniquely identify the exact subobject within the 
        most derived type (\textsection\ref{sec:vtp}).
  \item We also build an efficient cache indexing function for virtual table 
        pointers that minimizes the amount of conflicts 
        (\textsection\ref{sec:sovtp},\ref{sec:moc},\cite[\textsection 4.3.5]{TR}).
  \end{itemize}
\item We present a functional style pattern matching for C++ built as a library 
      employing the above technique. Our solution:
  \begin{itemize}
  \item Is open, non-intrusive and avoids the control inversion typical for visitors.
  \item Can be applied retroactively to any polymorphic or tagged class hierarchy.
  \item Provides a unified syntax for various encodings of extensible 
        hierarchycal datatypes in C++.
  \item Generalizes the controversial n+k patterns by leaving semantic choices to the user.
  \item Supports a limited form of views.
  \item Is simpler to use than conventional object-oriented or union-based alternatives.
  \item Improves performance compared to alternatives in real applications.
  \end{itemize}
\end{itemize}

\noindent
Our technique can be used in a compiler and/or library setting to implement 
facilities that depend on dynamic type or run-time properties of objects: e.g. 
type switching, type testing, pattern matching, predicate dispatch, 
multi-methods etc. We also look at different approaches to endoding algebraic 
data types in C++ and present a unified pattern-matching syntax that works 
uniformly with all of them. 
We generalize Haskell's n+k patterns\cite{haskell98} to any invertible operations. 
Semantics issues that typically accompany n+k pattern are handled transparently 
by forwarding the problem into the concepts domain, thanks to the fact that we 
work in a library setting. We also provide support for views in a form that 
resembles extractors in Scala. 

A practical benefit of our solution is that it can be used right away with any 
compiler with a decent support of C++0x without requiring the installation of 
any additional tools or preprocessors. The solution is a proof of concept that 
sets a minimum threshold for the performance, brevity, clarity and usefulness of 
a language solution for open type switching in C++.

The rest of this paper is structured as following. In Section~\ref{sec:bg}, we 
present evolution of pattern matching in different languages, presenting 
informally through example commonly used terminology and semantics of various 
pattern-matching constructs. Section~\ref{sec:adt} presents various approaches 
that are taken in C++ to encoding algebraic data types.
Sections~\ref{sec:syn} and~\ref{sec:sem} describe the syntax and semantics of 
our pattern matching facilities. Sections~\ref{sec:slv} and~\ref{sec:view} discuss 
approach taken by our library in handling generalized n+k patterns and views. 
Section~\ref{sec:impl} discusses techniques that makes type switching, used as a 
back-bone of the match statement, efficient, while section~\ref{sec:eval} 
provides its performance evaluation against some common alternatives. 
Section~\ref{sec:rw} discusses related work, and section~\ref{sec:cc} concludes 
by discussing some future directions and possible improvements.
